//给定一个整数 num，计算所有小于等于 num 的非负整数中数字 1 出现的个数。 
//
// 
//
// 示例 1： 
//
// 
//输入：num = 0
//输出：0
// 
//
// 示例 2： 
//
// 
//输入：num = 13
//输出：6 
//
// 
//
// 提示： 
//
// 
// 0 <= num < 10⁹ 
// 
//
// 注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/ 
//
// 
// Related Topics 递归 数学 动态规划 👍 470 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int digitOneInNumber(int num) {
        int count = 0;
        long i = 1; // 使用 long 以避免溢出

        while (i <= num) {
            long higher = num / (i * 10);
            long current = (num / i) % 10;
            long lower = num % i;

            if (current == 0) {
                count += higher * i;
            } else if (current == 1) {
                count += higher * i + lower + 1;
            } else {
                count += (higher + 1) * i;
            }

            i *= 10; // 移动到下一位
        }

        return count;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
